112. Path Sum
Easy

Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.

A leaf is a node with no children.

 

Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true

Example 2:

Input: root = [1,2,3], targetSum = 5
Output: false

Example 3:

Input: root = [1,2], targetSum = 0
Output: false

 

Constraints:

  • The number of nodes in the tree is in the range [0, 5000].
  • -1000 <= Node.val <= 1000
  • -1000 <= targetSum <= 1000
Accepted
635,046
Submissions
1,475,011
Seen this question in a real interview before?
Companies

Average Rating: 4.64 (36 votes)

Premium

Solution


Binary tree definition

First of all, here is the definition of the TreeNode which we would use in the following implementation.




Approach 1: Recursion

The most intuitive way is to use a recursion here. One is going through the tree by considering at each step the node itself and its children. If node is not a leaf, one calls recursively hasPathSum method for its children with a sum decreased by the current node value. If node is a leaf, one checks if the the current sum is zero, i.e if the initial sum was discovered.

Complexity Analysis

  • Time complexity : we visit each node exactly once, thus the time complexity is O(N)\mathcal{O}(N), where NN is the number of nodes.
  • Space complexity : in the worst case, the tree is completely unbalanced, e.g. each node has only one child node, the recursion call would occur NN times (the height of the tree), therefore the storage to keep the call stack would be O(N)\mathcal{O}(N). But in the best case (the tree is completely balanced), the height of the tree would be log(N)\log(N). Therefore, the space complexity in this case would be O(log(N))\mathcal{O}(\log(N)).


Approach 2: Iterations

Algorithm

We could also convert the above recursion into iteration, with the help of stack. DFS would be better than BFS here since it works faster except the worst case. In the worst case the path root->leaf with the given sum is the last considered one and in this case DFS results in the same productivity as BFS.

The idea is to visit each node with the DFS strategy, while updating the remaining sum to cumulate at each visit.

So we start from a stack which contains the root node and the corresponding remaining sum which is sum - root.val. Then we proceed to the iterations: pop the current node out of the stack and return True if the remaining sum is 0 and we're on the leaf node. If the remaining sum is not zero or we're not on the leaf yet then we push the child nodes and corresponding remaining sums into stack.

Current
1 / 8

Complexity Analysis

  • Time complexity : the same as the recursion approach O(N)\mathcal{O}(N).
  • Space complexity : O(N)\mathcal{O}(N) since in the worst case, when the tree is completely unbalanced, e.g. each node has only one child node, we would keep all NN nodes in the stack. But in the best case (the tree is balanced), the height of the tree would be log(N)\log(N). Therefore, the space complexity in this case would be O(log(N))\mathcal{O}(\log(N)).

Report Article Issue

Comments: 24
pidouki's avatar
Read More

If a stack there then it is dfs
Bfs should use a queue

31
Reply
Share
Report
s961206's avatar
Read More

For iteration version, it can also use pair:

public boolean hasPathSum(TreeNode root, int sum) {
   LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
   stack.add(new Pair(root, sum));
   while(!stack.isEmpty()){
       Pair<TreeNode, Integer> p = stack.poll();
       TreeNode node = p.getKey();
       int remain = p.getValue();
       if(node != null){
           remain -= node.val;
           if(node.left == null && node.right == null && remain == 0) return true;
           stack.add(new Pair(node.left, remain));
           stack.add(new Pair(node.right, remain));
       }
   }
   return false;
}

22
Show 3 replies
Reply
Share
Report
hongyu9310's avatar
Read More

I'm pretty sure this is DFS

node, curr_sum = de.pop()
if node.right: de.append(node.right, curr_sum - node.right.val)
if node.left: de.append(node.left, curr_sum - node.left.val)
<--- this is DFS (preorder: root, left, right)

node, curr_sum = de.pop(0)
if node.left: de.append(node.left, curr_sum - node.left.val)
if node.right: de.append(node.right, curr_sum - node.right.val)
<--- this is BFS

16
Reply
Share
Report
Xyzzy123's avatar
Read More

Terrible problem description: "Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum."

Consider the following initial conditions: "[], 0." This has no root, no leaves, and a zero sum. There is no root-to-leaf path.

The easy answer is "false." Since there is no root (much less any leaf), the result should be "false." However, this is inconsistent with this related problem, in which the lack of a root, and the lack of a leaf, isn't a problem.

https://leetcode.com/problems/minimum-depth-of-binary-tree/solution/

7
Show 1 reply
Reply
Share
Report
Mrunaol's avatar
Read More

Should be medium

15
Reply
Share
Report
sriharik's avatar
Read More

The recursive version is straightforward.

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        sum -= root.val;
        if (root.left == null && root.right == null) return sum == 0;
        return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);   
    }

However the iterative version we have to do a bit more thinking. But remember, we can emulate recursion iteratively with the help of a stack.

public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) return false;
        
        Stack<TreeNode> treeStack = new Stack<>();        
        Stack<Integer> sumStack  = new Stack<>();

        treeStack.add(root);
        sumStack.add(sum);
        
        while (!treeStack.isEmpty()) {
            TreeNode curr = treeStack.pop();
            int currVal = sumStack.pop() - curr.val;
            
            if (curr.left == null && curr.right == null && currVal == 0) return true;
            
            if (curr.left != null) {
                treeStack.push(curr.left);
                sumStack.push(currVal);
            }
            
            if (curr.right != null) {
                treeStack.push(curr.right);
                sumStack.push(currVal);
            }
        }
        
        return false;
    }

5
Reply
Share
Report
user5064Z's avatar
Read More

beats ~94%
Python3 BFS Solution
Instead of subtracting down to 0, I am adding up to the sum and checking that value on a leaf.

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False
        
        q = [(root,root.val)]
        while q:
            
            node,v = q.pop(0)
            
            if not node:
                continue
            
            if not node.left and not node.right:
                if v == sum:
                    return True
                continue
            
            if node.left:
                q.append((node.left,node.left.val + v))
            
            if node.right:
                q.append((node.right, node.right.val + v))
        return False

2
Reply
Share
Report
rahulkun's avatar
Read More

why would you need two stacks. Tree values can be mutated unless stated otherwise.

1
Reply
Share
Report
LeetMachine's avatar
Read More

@andvary Can this be done using morris traversal in constant space?

1
Show 2 replies
Reply
Share
Report
jca88's avatar
Read More

approach 1 is bottom up right? the return statement

return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)

could only have been answered if we answered the subproblems at the leaves. then we carry the answer up. is this right?

0
Show 1 reply
Reply
Share
Report
Success
Details
Runtime: 8 ms, faster than 88.78% of C++ online submissions for Path Sum.
Memory Usage: 21.3 MB, less than 21.86% of C++ online submissions for Path Sum.
Next challenges:
Time Submitted
Status
Runtime
Memory
Language
06/15/2021 20:31Accepted8 ms21.3 MBcpp
08/18/2020 19:32Accepted20 ms21.1 MBcpp
06/04/2020 15:03Accepted16 ms22.4 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.